import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;



public class Clustering {

	class Edge{
		int start;
		int end;
		int distance;
	}
	
	class Vertex{
		Vertex head;
		int index;
		int rank;
	}
	
	private ArrayList<Edge> edges;
	private ArrayList<Vertex> groups;
	private int count;
	
	public void InitData(){
		DataReader reader = new DataReader();
		reader.SetFilename("D:\\algorithm\\part2\\wk2\\clustering1.txt");
		
		String str;
		str = reader.GetNextLine();
		String[] parser = str.split(" ");
		count = Integer.parseInt(parser[0]);
		edges = new ArrayList<Edge>(count * (count - 1) / 2);		
		
		while((str = reader.GetNextLine()) != null)
		{
			Edge edge = new Edge();
			parser = str.split(" ");
			edge.start = Integer.parseInt(parser[0]);
			edge.end = Integer.parseInt(parser[1]);
			edge.distance = Integer.parseInt(parser[2]);
			
			edges.add(edge);
		}
		groups = new ArrayList<Vertex>(count);
		for(int i = 0; i < count; i++)
		{
			Vertex ver = new Vertex();
			ver.head = ver;
			ver.index = i + 1;
			ver.rank = 0;
			groups.add(ver);
		}
	}
	
	public void PrintData(){
		for(int i = 0; i < edges.size(); i++)
		{
			Edge edge = edges.get(i);
			System.out.print(edge.start + " " + edge.end + " " + edge.distance + "\n");
		}
	}
	
	private boolean IsInSameGroup(Vertex v1, Vertex v2){
		Vertex head1 = GetHead(v1);		
		Vertex head2 = GetHead(v2);		
		
		if(head1 == head2)
			return true;
		else
			return false;
	}
	
	
	private Vertex GetHead(Vertex v)
	{
		Vertex head = v.head;
		while(head != v)
		{
			v = head;
			head = v.head;
		}
		
		return head;
	}
	
	private void MergeTwoGroups(Vertex v1, Vertex v2){
		Vertex head1 = GetHead(v1);
		Vertex head2 = GetHead(v2);
		
		if(head1.rank >= head2.rank)
		{
			head2.head = head1;
		}
		else{
			head1.head = head2;
		}
	}
	
	
	public void RunClurstering(){		
		Collections.sort(edges, new Comparator<Edge>(){
			public int compare(Edge e1, Edge e2){
				if(e1.distance > e2.distance)
					return 1;
				else if(e1.distance < e2.distance)
					return -1;
				else 
					return 0;
			}
		});
		
		int i = count;
		int cur = 0;
		Edge e;
		while(i > 4)
		{
			e = edges.get(cur);
			Vertex v1 = groups.get(e.start - 1);
			Vertex v2 = groups.get(e.end - 1);
			if(!IsInSameGroup(v1, v2))
			{
				i--;
				MergeTwoGroups(v1, v2);
			}
			cur++;
			System.out.print(e.start + "\t" + e.end + "\t" + e.distance + "\n");
		}		
		
		while(true)
		{
			e = edges.get(cur);
			Vertex v1 = groups.get(e.start - 1);
			Vertex v2 = groups.get(e.end - 1);
			if(!IsInSameGroup(v1, v2))
			{
				System.out.print("max spacing is " + e.distance + "\n");
				break;
			}
			cur++;
		}
	}
}
